EM算法：Expectation-maximization algorithm
Wiki定义 最大期望算法，是在概率模型中寻找参数最大似然估计或者最大后验估计的算法。其中概率模型依赖于无法观测的隐性变量。
- EM算法经过两个步骤交替进行计算 1. 计算期望E, 利用对隐藏变量的现有估计值，计算其极大似然估计值 2. 最大化(M), 最大化在E步上球的的最大似然值来计算参数的值。M步上找到的参数估计值被用于下一个E步计算中，这个过程不断交替进行。
EM算法公式推导：
1. EM算法目标函数
假设我们有一个样本集{x(1),…,x(m)}，包含m个独立的样本，现在我们想找到每个样本隐含的类别z，能使得p(x,z)最大。p(x,z)的极大似然估计如下：
对于参数估计，本质上还是想获得一个使得似然函数最大化的参数θ，现在与极大似然不同的只是似然函数式中多了一个未知的变量z，见下式（1）。也就是说我们的目标是找到适合的θ和z，以让L(θ)最大。那我们也许会想，你就是多了一个未知的变量而已啊，我也可以分别对未知的θ和z分别求偏导，再令其等于0，求解出来不也一样吗？
本质上我们是需要最大化（1）式，也就是似然函数，但是可以看到里面有“和的对数”，求导后形式会非常复杂（自己可以想象下log(f1(x)+ f2(x)+ f3(x)+…)复合函数的求导），所以很难求解得到未知参数z和θ。
我们把分子分母同乘以一个相等的函数（即隐变量Z的概率分布Qi(z(i))，其概率之和等于1，即
），即得到上图中的（2）式，但（2）式还是有“和的对数”，还是求解不了，咋办呢？接下来，便是见证神奇的时刻，我们通过Jensen不等式可得到（3）式，此时（3）式变成了“对数的和”，如此求导就容易了。
从（2）式到（3）式，神奇的地方有两点：
- 当我们在求（2）式的极大值时，(2)式不太好计算，我们便想（2）式大于某个方便计算的下界（3）式，而我们尽可能让下界（3）式最大化，直到（3）式的计算结果等于（2）式，便也就间接求得了（2）式的极大值；
回到公式（2），因为f(x)=log x为凹函数（其二次导数为-1/x2<0）。
这个式子经过转换之后变成（3）式的不等式！
OK，到这里，现在式(3)就容易地求导了，但是式(2)和式(3)是不等号啊，式(2)的最大值不是式(3)的最大值啊，而我们想得到式(2)的最大值，那怎么办呢？
上面的式(2)和式(3)不等式可以写成：似然函数L(θ)>=J(z,Q)，如3.1节最后所说，我们可以通过不断的最大化这个下界J，来使得L(θ)不断提高，最终达到L(θ)的最大值。
见上图，我们固定θ，调整Q(z)使下界J(z,Q)上升至与L(θ)在此点θ处相等（绿色曲线到蓝色曲线），然后固定Q(z)，调整θ使下界J(z,Q)达到最大值（θt到θt+1），然后再固定θ，调整Q(z)……直到收敛到似然函数L(θ)的最大值处的θ*。
这里有两个问题：
- 什么时候下界J(z,Q)与L(θ)在此点θ处相等？
- 为什么一定会收敛？
首先第一个问题，在Jensen不等式中说到，当自变量X是常数的时候，等式成立。换言之，为了让（3）式取等号，我们需要：
其中，c为常数，不依赖于zi。对该式做个变换，并对所有的z求和，得到
因为前面提到
（对的，隐变量Z的概率分布，其概率之和等于1），所以可以推导出：
所以通过
，可求得的值
，加之，所以
为
瞬间豁然开朗！至此我们推出了在固定参数θ后，使下界拉升的Q(z)的计算公式就是条件概率，解决了Q(z)如何选择的问题。这一步就是E步，建立L(θ)的下界。
接下来的M步，就是在给定Q(z)后，调整θ，去极大化L(θ)的下界J(z,Q)，毕竟在固定Q(z)后，下界还可以调整的更大。
这就是EM算法的步骤。
EM应用例子：
1. 网球心态/好球率分析
网球比赛中，心态的好坏会极大地影响运动员的击球表现。虽然你可以从选手的表情中看出来一些他现在的心态，但更精准的判断心态的方式还是看他在这一时间段内的击球质量。现在我们有一位运动员在一场比赛中，不同时间段内的球质数据。
| 时间段 | 击球质量序列 |
|---|---|
| SET1 | GOOD, BAD,BAD,BAD |
| SET2 | GOOD, GOOD, BAD,BAD |
| SET2 | GOOD, BAD, GOOD, GOOD |
| SET4 | GOOD, GOOD, GOOD, GOOD |
假设运动员的心理状态有两种情况
- 冷静
- 焦躁
现在我们要根据不同时间段内的击球质量序列
- 来预测该选手在不同心理状态下的击球质量的概率数据。 - 目标：得到选手在不同心理状态下的击球质量概率分布 - 隐变量：心理状态 在这个数据中，我们无法知道某个时间段内选手的心态如何，但是我们可以通过一个合理的假设：
- 一段比赛时间内的心态越好，越有可能打出更高球质的球。 来假定一个球员在不同心态下的击球准确度，再根据 EM算法来预测他在特定时间段内的心态，再根据预测出的心态来更新他们在不同心理状态的击球质量。如此反复循环，我们就可以得到一个固定下来的，在不同心理状态下的击球质量的概率数据。依次来获得这个球员的实力信息，以供教练参考。
实现
EM算法的具体应用：
-
初始化：
- 首先，我们假设有关于在冷静和焦躁两种状态下的击球质量的初步假设或先前的数据。
- 例如，我们可能会初始化假设，一个冷静的状态下，击球质量为GOOD的概率为0.8，而焦躁状态下为0.3。
-
E步骤（Expectation）：
- 接下来，使用这些初始概率，我们为每个时间段的击球序列计算属于冷静或焦躁状态的概率。
- 例如，一个时间段内如果有3个GOOD和1个BAD，我们会计算在冷静状态下观测到这种序列的概率，和在焦躁状态下观测到这种序列的概率。
-
M步骤（Maximization）：
- 然后，我们利用E步骤得到的数据来重新估计在冷静和焦躁两种心理状态下的击球质量分布的概率。
- 这意味着调整我们的假设以最大化观测数据的可能性。
-
迭代：
- 重复E步骤和M步骤，直到达到一定的收敛条件，例如参数变化小于某个阈值或达到预定的迭代次数。
通过这种方法，我们可以更准确地估计一个运动员在不同心理状态下的表现，并可能进一步用这些信息来指导训练，例如，通过心理训练提高在焦躁状态下的表现，或者通过不同的比赛策略来维持冷静的状态。